#include <iostream>
#include <vector>
using namespace std;
#define MVNum 100
typedef char VerTexType;//顶点数据类型设置为字符
typedef int ArcType;//边的权值为整型
typedef int OtherInfo;

/*********邻接矩阵***********/
struct AMGraph {
	VerTexType vexs[MVNum];//顶点表
	ArcType arcs[MVNum][MVNum];//邻接矩阵
	int vexnum;//顶点数量
	int	arcnum;//边数量
};


int Locatevex(AMGraph G, VerTexType v)//定位顶点下标
{
	for (int i = 0; i < G.vexnum; i++)//遍历寻找对应顶点下标
	{
		if (G.vexs[i]==v)
		{
			return i;
		}
	}
	return -1;
}
void CreateUDN(AMGraph&G, int vex_num, int edge_num)
{
	G.vexnum = vex_num;
    G.arcnum = edge_num;

	cout << "请输入各顶点信息：" << endl;
	for (int i = 0; i < G.vexnum; i++)//请输入各顶点信息
	{
		cin >> G.vexs[i];
	}


	for (int i = 0; i < G.vexnum; i++)//将邻接矩阵初始化为0
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			G.arcs[i][j] = 0;
		}
	}
	for (int k = 0; k < G.arcnum; k++)
	{
		VerTexType v1, v2;
		int w;
		cout << "请依次输入第"<<k+1<<"条边的两个顶点及权值：";
		cin >> v1 >> v2 >> w;
		int i = Locatevex(G, v1);//找到顶点在图中边的下标
		int j = Locatevex(G, v2);
		if (i != -1 && j != -1)//如果能找到对应顶点，对边赋权值
		{
			G.arcs[i][j] = w;
		}
        else
        {
            cout << "顶点输入错误，请重新检查!" << endl;//顶点输入错误处理
            k-=1;
        }
	}
}

void Bellman_ford(AMGraph &G)
{
	VerTexType begin;
	VerTexType end;
	cout << "请输入起末段" << endl;
	cin >> begin >> end;
	int dist[G.vexnum];
	int src = Locatevex(G, begin);
	int target = Locatevex(G, end);


	for (int i = 0; i < G.vexnum; i++)
	{
		if (i==src)
		{
			dist[i] = 0;
		}
		else
		{
			dist[i] = 65535;
		}
	}
	for (auto i:dist)
	{
		cout << i << endl;
	}

	int last_update[G.vexnum];
	for(int i = 0; i < G.vexnum; i++)
	{
		if(dist[i]==65535)
		{
			last_update[i] = -1;
		}
		else
		{
			last_update[i] = src;
		}
	}

	for(int i = 0; i < G.vexnum; i++)
	{
		bool change = false;
		for (int j = 0; j < G.vexnum; j++)
		{
			for (int k = 0; k < G.vexnum; k++)
			{
				if (G.arcs[k][j] != 0)
				{
					if (dist[j]>dist[k]+G.arcs[k][j])
					{
						dist[j] = dist[k] + G.arcs[k][j];
						last_update[j] = k;
						change = true;
					}
				}					
			}
		}
		if (!change) break;
	}

	for (auto i:dist)
	{
		cout << i << endl;
	}
	cout << "最短路径长为：" << dist[target] <<endl;

	
    for(int i = 0; i < G.vexnum; i++)
	{
		for (int j = 0; j < G.vexnum; j++)
		{
			if(dist[j] > dist[i] + G.arcs[i][j])
				cout << "存在负权回路" <<endl;
				break;
		}
	}

	cout << "最短路径为";
	vector<int> path;
	int tmp = target;
    while (tmp != src)
	{
		path.push_back(tmp);
        tmp = last_update[tmp];
	}
	for(int i=path.size();i>0;--i)
	{
		cout << G.vexs[path[i]] << "->";
	}
	cout <<G.vexs[target] << endl;
}

void listVertexes(AMGraph &g)
{
    for (int i = 0; i < g.vexnum; i++)//输出邻接表
    {
        cout << "第" << i + 1 << "个顶点：" << g.vexs[i] << endl;
    }
}

void listEdges(AMGraph &g)
{
    int k = 1;
    for (int i = 0; i < g.vexnum; i++)//输出邻接矩阵
    {	
        for (int j = 0; j < g.vexnum; j++)
        {
            if (g.arcs[i][j] != 0)
            {
                cout << "第" << k << "条边" << ": (" << g.vexs[i] << "," << g.vexs[j] << "," << g.arcs[i][j] << ")"  << endl;
                k++;
            }
        }
    }
}



/*********邻接表***********/

struct ArcNode {
	int adjvex;//连接的顶点下标
	struct ArcNode *nextarc;//下一节点
	OtherInfo info;//权值
};
struct VNode{
	VerTexType data;//顶点数据
	ArcNode *firstarc;//边的连接点
};
struct ALGraph{
	int vexnum;//顶点总数
	int arcnum;//边总数
    VNode vertices[MVNum];//顶点数组
};


int Locatevex(ALGraph G, VerTexType v)//定位顶点下标
{
	for (int i = 0; i < G.vexnum; i++)//遍历寻找对应顶点下标
	{
		if (G.vertices[i].data == v)
		{
			return i;
		}
	}
	return -1;
}
void CreateUDG(ALGraph &G, int vex_num, int edge_num)
{
    G.vexnum = vex_num;
    G.arcnum = edge_num;
	cout << "请输入各顶点信息：" << endl;
	for (int i = 0; i < G.vexnum; i++)//请输入各顶点信息
	{
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;
	}
	for (int k = 0; k < G.arcnum; k++)
	{
		VerTexType v1, v2;
		int w;
		cout << "请依次输入" << k << "条边的两个顶点及权值：";
		cin >> v1 >> v2 >> w;
		int i = Locatevex(G, v1);//找到顶点在图中边的下标
		int j = Locatevex(G, v2);
        if (i != -1 && j != -1)//如果能找到对应顶点，对边赋权值
        {
            /*ArcNode *p1 =new ArcNode;//边用前插法插入到顶点后方
            p1->info = w;
            p1->adjvex = i;
            p1->nextarc = G.vertices[j].firstarc;
            G.vertices[j].firstarc= p1;*/
            ArcNode *p2 = new ArcNode;
            p2->info = w;
            p2->adjvex = j;
            p2->nextarc = G.vertices[i].firstarc;
            G.vertices[i].firstarc = p2;
        }
        else
        {
            cout << "顶点输入错误，请重新检查!" << endl;//顶点输入错误处理
        } 	
	}
}

void listVertexes(ALGraph &g)
{
    for (int i = 0; i < g.vexnum; i++)//输出邻接表
    {
        cout << "第" << i + 1 << "个顶点：" << g.vertices[i].data << endl;
    }
}

void listEdges(ALGraph &g)
{
    for (int i = 0; i < g.vexnum; i++)//输出邻接表
    {
        int k = 1;
        ArcNode *p = g.vertices[i].firstarc;
        while (p)
        {
            cout << "第" << k << "条边" << ": (" << g.vertices[i].data << "," << g.vertices[p->adjvex].data << "," <<  p->info << ")"  << endl;
            p = p->nextarc;
            k++;
        }
        }
}